package com.lw.leetcode.dp.b;

import java.util.Arrays;

/**
 * 1314. 矩阵区域和
 *
 * @Author liw
 * @Date 2021/5/29 17:57
 * @Version 1.0
 */
public class MatrixBlockSum {

    public static void main(String[] args) {
        MatrixBlockSum test = new MatrixBlockSum();
        // [[12,21,16],[27,45,33],[24,39,28]]
        int[][] arr = {{1,2,3},{4,5,6},{7,8,9}};
        int[][] ints = test.matrixBlockSum(arr, 1);
        for (int[] anInt : ints) {
            System.out.println(Arrays.toString(anInt));
        }
    }

    public int[][] matrixBlockSum(int[][] mat, int k) {
        int a = mat.length;
        int b = mat[0].length;
        int[][] arr = new int[a + 1][b + 1];
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                arr[i + 1][j + 1] = arr[i + 1][j] + arr[i][j + 1] - arr[i][j] + mat[i][j];
            }
        }
        int[][] values = new int[a][b];
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                int s1 = i + 1 + k > a ? a : i + 1 + k;
                int s2 = j + 1 + k > b ? b : j + 1 + k;
                int e1 = i - k < 0 ? 0 : i - k;
                int e2 = j - k < 0 ? 0 : j - k;
                values[i][j] = arr[s1][s2] - arr[e1][s2] - arr[s1][e2] + arr[e1][e2];
            }
        }
        return values;
    }
}
